#ifndef QUAD_TREE_NODE_HPP
#define QUAD_TREE_NODE_HPP

////////////////////////////////////////////////////////////
// Headers
////////////////////////////////////////////////////////////
#include <assert.h>
#include <unordered_set>
#include <vector>

#include <SmegTools/Config.h>

#include "../../Entity/BaseObject.hpp"
#include "../BoundingVolumes/BoundingBox.hpp"

#ifdef _DEBUG
namespace sf {
    class RenderWindow;
}
#endif

#include <SmegTools/Debug/DebugNew.hpp>

namespace smeg {
    namespace math {

class QuadTree;

////////////////////////////////////////////////////////////
/// Represents a Node of a QuadTree
////////////////////////////////////////////////////////////
class QuadTreeNode
{
    typedef    std::unordered_set< core::BaseObject* >              td_OccupantsSet;
    typedef    std::unordered_set< core::BaseObject* >::iterator    td_OccupantsSetIt;

    ////////////////////////////////////////////////////////////
    /// Copy Constructor
    ////////////////////////////////////////////////////////////
    QuadTreeNode( const QuadTreeNode& _Copy ) {}

public:
    ////////////////////////////////////////////////////////////
    /// Default constructor
    /// 
    ////////////////////////////////////////////////////////////
                                    QuadTreeNode();
    ////////////////////////////////////////////////////////////
    /// Constructor
    ///
    /// \param _Region :            Region this node represents
    /// \param _pTree :             Tree this node is in
    /// \param _pParent :           Parent node
    /// \param _uLevel :            Level of this node in the tree
    ///
    ////////////////////////////////////////////////////////////
                                    QuadTreeNode( const math::BoundingBox& _Region, QuadTree* _pTree, QuadTreeNode* _pParent = NULL, const unsigned _uLevel = 0 );
    ////////////////////////////////////////////////////////////
    /// Destructor
    ///
    ////////////////////////////////////////////////////////////
    virtual                         ~QuadTreeNode();
    
    ////////////////////////////////////////////////////////////
    /// Create the node
    ///
    /// \param _Region :            Region this node represents
    /// \param _pTree :             Tree this node is in
    /// \param _pParent :           Parent node
    /// \param _uLevel :            Level of this node in the tree
    ///
    ////////////////////////////////////////////////////////////
    void                            Create( const math::BoundingBox& _Region, QuadTree* _pTree, QuadTreeNode* _pParent = NULL, const unsigned _uLevel = 0 );
    ////////////////////////////////////////////////////////////
    /// Try to add an occupant to this node
    ///
    /// \param _pNewOccupant :      Occupant to add
    ///
    /// \return Whether the occupant was added to the node or not
    ///
    ////////////////////////////////////////////////////////////
    bool                            Add( core::BaseObject* _pNewOccupant );
    ////////////////////////////////////////////////////////////
    /// Update the occupation of this node with the given occupant
    /// This function check the occupant's containment, it either :
    ///     - let the occupant at this level 
    ///     - put the occupant in the node's children or in the node's parent
    ///     - remove the occupant from this node and add it outside the tree
    ///
    /// \param _pNewOccupant :      Occupant to add
    ///
    ////////////////////////////////////////////////////////////
    void                            Update( core::BaseObject* _pOccupant );
    ////////////////////////////////////////////////////////////
    /// Remove the occupation from this node
    ///
    /// \param _pNewOccupant :      Occupant to remove
    ///
    ////////////////////////////////////////////////////////////
    void                            Remove( core::BaseObject* _pOccupant );
    ////////////////////////////////////////////////////////////
    /// Retrieve the occupants in this node and its children
    ///
    /// \param _Occupants :         Output vector of occupants
    ///
    ////////////////////////////////////////////////////////////
    void                            GetAllOccupantsBelow( std::vector< core::BaseObject* >& _Occupants, BoundingVolume::eBoundingVolume _eType = BoundingVolume::eAny );

    /*********************** Accessors ************************/
    const td_OccupantsSet&          GetOccupants() const;
    const math::BoundingBox&               GetRegion() const;
    QuadTree*                       GetTree() const;
    QuadTreeNode*                   GetParentNode() const;
    unsigned                        GetLevel() const;
    bool                            HasChildren() const;
    QuadTreeNode*                   GetChild( const unsigned _uX, const unsigned _uY );

private:
    ////////////////////////////////////////////////////////////
    /// Destroy all children
    ///
    ////////////////////////////////////////////////////////////
    void                            DestroyChildren();
    ////////////////////////////////////////////////////////////
    /// Partition the node into 4 children nodes
    ///
    ////////////////////////////////////////////////////////////
    void                            Partition();
    ////////////////////////////////////////////////////////////
    /// Merge the children into this node
    ///
    ////////////////////////////////////////////////////////////
    void                            Merge();
    
    ////////////////////////////////////////////////////////////
    /// Get the node that could contains _pNewOccupant, this node is the one containing the center of _pNewOccupant
    ///
    /// \param _pNewOccupant :      Occupant to check
    ///
    ////////////////////////////////////////////////////////////
    QuadTreeNode*                   GetNodeContaining( core::BaseObject* _pNewOccupant );

    ////////////////////////////////////////////////////////////
    /// Add an occupant to this level
    ///
    /// \param _pNewOccupant :      Occupant to add
    ///
    ////////////////////////////////////////////////////////////
    void                            AddToThisLevel( core::BaseObject* _pNewOccupant );
    ////////////////////////////////////////////////////////////
    /// Add an occupant to this node's children
    ///
    /// \param _pNewOccupant :      Occupant to add
    ///
    /// \return Whether the occupant was added to the children's node or not
    ///
    ////////////////////////////////////////////////////////////
    bool                            AddToChildren( core::BaseObject* _pNewOccupant );
    
    /********************* Private members ********************/
    math::BoundingBox                      m_Region;                   /// Region representing this node
    QuadTree*                       m_pTree;                    /// Tree this node is in
    QuadTreeNode*                   m_pParentNode;              /// Parent node (can be NULL)
    unsigned                        m_uLevel;                   /// Level of this node in the tree

    unsigned                        m_uNumOccupantsBelow;       /// Number of occupants this node and its children has
    td_OccupantsSet                 m_Occupants;                /// Occupants of this node
    
    bool                            m_bHasChildren;             /// Does this node has children
    std::vector< std::vector<QuadTreeNode*> >    m_Children;    /// Vector of children nodes

#ifdef _DEBUG
public:
    void                            DebugRender( sf::RenderWindow* _pRenderWindow, const sf::Color& _Color = sf::Color::White ) const;
#endif // _DEBUG
};

/************************** Inline ************************/
inline const QuadTreeNode::td_OccupantsSet& QuadTreeNode::GetOccupants() const {
    return m_Occupants;
}

inline const math::BoundingBox& QuadTreeNode::GetRegion() const {
    return m_Region;
}

inline QuadTree* QuadTreeNode::GetTree() const {
    return m_pTree;    
}

inline QuadTreeNode* QuadTreeNode::GetParentNode() const {
    return m_pParentNode;
}

inline unsigned QuadTreeNode::GetLevel() const {
    return m_uLevel;
}

inline bool QuadTreeNode::HasChildren() const {
    return m_bHasChildren;
}

inline QuadTreeNode* QuadTreeNode::GetChild( const unsigned _uX, const unsigned _uY ) {
    assert( _uX >= 0 && _uX < 2 && _uY >= 0 && _uY < 2 );
    return m_Children[_uX][_uY];
}

    } // namespace light
} // namespace smeg

#include <SmegTools/Debug/DebugNewOff.hpp>

#endif // QUAD_TREE_NODE_HPP
